package cn.javadog.algorithm.e1_100;


/**
 * 二进制求和
 * https://leetcode-cn.com/problems/add-binary/
 * @author Sprite
 */
public class Algorithm67 {
	public static void main(String[] args) {
		String A = "1010";
		String B = "1011";
		String binary = addBinary(A, B);
		System.out.println(binary);
	}

	public static String addBinary(String a, String b) {
		String[] as = a.split("");
		String[] bs = b.split("");
		int minLen = Math.min(as.length, bs.length);
		int maxLen = Math.max(as.length, bs.length);
		String[] temp = new String[maxLen];
		for (int i = 0; i < minLen; i++) {
			// 填充后半部分
			temp[maxLen-1-i] = as[as.length-1-i] + bs[bs.length-1-i];
		}
		// 单独填充前半部分
		if (as.length>bs.length){
			System.arraycopy(as,0,temp,0,maxLen-minLen);
		}else if (bs.length>as.length){
			System.arraycopy(bs,0,temp,0,maxLen-minLen);
		}
		//计算
		StringBuilder sb = new StringBuilder();
		boolean over = false;
		for (int i = temp.length-1; i >=0 ; i--) {
			if (over){
				if ("11".equals(temp[i])){
					sb.append("1");
					over = true;
				}else if (temp[i].contains("1")){
					sb.append("0");
					over = true;
				}else {
					sb.append("1");
					over = false;
				}
			}else {
				if ("11".equals(temp[i])){
					sb.append("0");
					over = true;
				}else if (temp[i].contains("1")){
					sb.append("1");
					over = false;
				}else {
					sb.append("0");
					over = false;
				}
			}
		}

		if (over) sb.append("1");

		return sb.reverse().toString();
	}
}
